package com.zdp.leetcodeMiddle;


import java.util.Stack;

/*
* 题目描述：
* 请根据每日 气温 列表，重新生成一个列表。
* 对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。
* 如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，
* 你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。
* 每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/daily-temperatures
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 每日温度_739 {
    public static void main(String[] args) {
        每日温度_739 demo  = new 每日温度_739();
        int[] T = new int[]{
                34,80,80,34,34,80,80,80,80,34
        };
        int[] ints = demo.dailyTemperatures(T);
        for(int i : ints){
            System.out.println(i);
        }
    }

    /*
    * 解题思路：
    *  换个思路 从后向前遍历
    *  然后用一个数组 存储 当前数 最接近当前数的大于当前数的位置
    *   接下来寻找 就可以利用这个数组了
    * */
    public int[] dailyTemperatures(int[] T) {
        int length = T.length;
        int[] result1 = new int[length];
        for(int i=length-2;i>=0;i--){
            if(T[i] < T[i+1]){
                result1[i] = i+1;
            }else{
                // 如果是大于等于的话  利用 result1数组
                int j = result1[i+1];
                while(T[i] >= T[j] && j!=0){
                    j = result1[j];
                }
                result1[i] = j;
            }
        }
        // 生成一下答案  距离观测到更高气温的天数 只要将更高气温的天数减去当前天数即可
        for(int i = 0;i<length-1;i++){
            if(result1[i] == 0){
                continue;
            }
            result1[i] = result1[i] - i;
        }
        return result1;
    }

    /*
    * 也可以使用单调栈
    *  每次遍历一个元素，都将其与 单调栈中的栈底元素的气温进行比较
    * 如何气温大于单调栈 栈顶元素，则将栈顶元素出栈，然后算出天数
    * 如何气温小于单调栈栈顶元素，则入栈
    * */
    public int[] dailyTemperatures1(int[] T) {
        int[] result = new int[T.length];
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<T.length;i++){
                // 栈不为空 进行比较
                // 直到 栈顶元素的温度小于 当前元素
                while(!stack.isEmpty() && T[i] > T[stack.peek()]  ){
                    // 出栈 计算天数
                    int day = stack.pop();
                    result[day] = i-day;
                }
                stack.push(i);
        }
        return result;
    }
}
